Lazy Segment Tree
Operations
モノイド$ (M, *)の列$ a_1, a_2, \dots, a_nと，列に対する「作用」を扱う．作用は次のように表現される：
作用素としてのモノイド$ (E, \cdot)
作用としての写像$ f: M \times E \rightarrow M
以下を満たす
任意の$ a, b \in M, p \in Eについて$ f(a * b, p) = f(a, p) * f(b, p)
演算後に作用させた結果は, 演算前に作用させた結果に等しい
作用は$ \astに対して分配的
任意の$ a \in M, p, q \in Eについて$ f(f(a, p), q) = f(a, q \cdot p)
二つの作用素を順に作用させた結果は, それらの作用素を先に結合してから作用させた結果に等しい
$ eを$ Eの単位元とすると，任意の$ a \in Mについて $ f(a, e) = a
作用が区間の要素数に比例して変化してもよい
そのときは一番目の条件だけ変化する
$ p \in E, k \in \mathbb{N}について, $ \overbrace{p \cdot \ldots \cdot p}^{k}を$ p^kと表現する
任意の$ a, b \in M, p \in E, k \in \mathbb{N}について$ f(a*b, p^{2k}) = f(a, p^{k}) * f(b, p^{k})
空間計算量$ \Theta(n)
$ \mathtt{new}()
列の項がすべて$ Mの単位元であるLazy Segment Treeを作成する
時間計算量 $ \Theta(n)
$ \mathtt{build}(a_1, a_2, \dots, a_n)
与えられた列を表現するLazy Segment Treeを作成する
時間計算量 $ \Theta(n)
$ \mathtt{effect}(l, r, e)
$ a_l, a_{l+1}, \dots, a_rをそれぞれ$ eによる作用で$ f(a_l, e), f(a_{l+1}, e), \dots, f(a_r, e)にする
時間計算量 $ \Omicron(\log n)
$ \mathtt{fold}(l, r)
$ a_l * a_{l+1} * \dots * a_rを計算する
時間計算量 $ \Omicron(\log n)
Summary
Lazy Segment Tree の各ノードには$ Mの値だけでなく, 遅延伝搬する$ Eの値と遅延伝搬する値があるかどうかのtoggleを持つ.
根から再帰的にノードにアクセスする際, 下の子に遅延伝搬をする$ \mathtt{push}を毎回する.
遅延伝搬を表現する図がほしい
References
Notes
遅延伝搬セグメント木と表現するのが◎
Lazy Segment Treeも非再帰で実装できるらしい
Implementations
Problems